using System;
using System.Collections.Generic;

namespace Squamous.Map
{
	/* A class to generate 2D grid maps of arbitrary value type.
	 * To use, specialise the generic class to the type you want stored
	 * in your 2D grid map, then call the Generate method.
	 */
	public class VoronoiMapGenerator<T>
	{
		/* Call this method to generate the map.
		 * Specify the dimensions of the map you want, a list of values that the grid cells
		 * should take and a random number generator.
		 */
		public static T[,] Generate(uint width, uint height, List<T> seedValues, Random rand)
		{
			T[,] result = new T[width, height];
			
			uint area = width * height;
			uint seedCount = area / 3;	// 1/3 of the area seems to work well.
			
			// Generate the random seed points that will be the centres of the Voronoi diagram cells.
			Point[] seedPoints = new Point[seedCount];
			for(uint i = 0; i < seedCount; i++)
			{
				seedPoints[i].x = rand.NextDouble() * width;
				seedPoints[i].y = rand.NextDouble() * height;
				seedPoints[i].value = seedValues[rand.Next(seedValues.Count)];
			}
			
			// Generate the map cell by cell.
			for(uint x = 0; x < width; x++)
			{
				for(uint y = 0; y < height; y++)
				{
					// Find the closest seed point to the cell.
					double closestDist = double.MaxValue;
					T closestVal = default(T);
					foreach(Point seedPoint in seedPoints)
					{
						double dx = (double) x - seedPoint.x;
						double dy = (double) y - seedPoint.y;
						double dist = Math.Sqrt(dx * dx + dy * dy);
						if(dist < closestDist)
						{
							closestDist = dist;
							closestVal = seedPoint.value;
						}
					}
					
					// Set the map cell to the closest seed point value.
					result[x, y] = closestVal;
				}
			}
			
			return result;
		}
		
		/* This is an internal POD (plain old data) structure to hold
		 * the position of the seed values used in the map generation.
		 */
		private struct Point
		{
			public double x;
			public double y;
			public T value;
		}
	}
}
